#include "heap.h"

#define PARENT(index) 		((index+1)/2-1)
#define LEFT_CHILD(index) 	((index+1)*2-1) 
#define RIGHT_CHILD(index) 	((index+1)*2)

#define swap_mem(p1,p2,size) do{	\
	char temp[size];				\
	memcpy(temp,p1,size);			\
	memcpy(p1,p2,size);				\
	memcpy(p2,temp,size);			\
}while(0)

#define swap(a,b) swap_mem(&a,&b,sizeof(a))

// 创建空堆
Heap* create_heap(size_t cal,Comper cmp)
{
	Heap* heap = malloc(sizeof(Heap));
	heap->base = malloc(sizeof(void*)*cal);
	heap->cal = cal;
	heap->cmp = cmp;
	heap->cnt = 0;
	return heap;
}

// 销毁堆
void destroy_heap(Heap* heap)
{
	free(heap->base);
	free(heap);
}

// 清空堆
void clear_heap(Heap* heap)
{
	heap->cnt = 0;
}

// 入堆
bool push_heap(Heap* heap,void* ptr)
{
	if(full_heap(heap))
		return false;
	
	int index = heap->cnt++;
	heap->base[index] = ptr;

	// index处向上调整
	while(index > 0)
	{
		int parent = PARENT(index);
		int left = LEFT_CHILD(parent), right = RIGHT_CHILD(parent);

		if(left < heap->cnt && 
			-1 == heap->cmp(heap->base[left],heap->base[parent]))
			swap(heap->base[left],heap->base[parent]);
		if(right < heap->cnt && 
			-1 == heap->cmp(heap->base[right],heap->base[parent]))
			swap(heap->base[right],heap->base[parent]);

		index = parent;
	}

	return true;
}

// 出堆
bool pop_heap(Heap* heap)
{
	if(empty_heap(heap))
		return false;

	heap->base[0] = heap->base[--heap->cnt];
	
	int parent = 0;
	while(parent < heap->cnt)
	{
		int max = parent;
		int left = LEFT_CHILD(parent), right = RIGHT_CHILD(parent);

		if(left < heap->cnt && 
			-1 == heap->cmp(heap->base[left],heap->base[max]))
			max = left;
		if(right < heap->cnt && 
			-1 == heap->cmp(heap->base[right],heap->base[max]))
			max = right;

		if(max == parent)
			break;

		swap(heap->base[parent],heap->base[max]);
		parent = max;
	}
	return true;
}

// 判断堆是否空
bool empty_heap(Heap* heap)
{
	return 0 == heap->cnt;
}

// 判断堆是否满
bool full_heap(Heap* heap)
{
	return heap->cal == heap->cnt;
}

// 获取堆元素的数量
size_t size_heap(Heap* heap)
{
	return heap->cnt;
}

// 查看堆顶
void* top_heap(Heap* heap)
{
	return heap->base[0];
}


